import java.util.*;

//返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序
public class Solution {
    public class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public static List<String> topKFrequent(String[] words, int k){
        //1.统计单词出现的个数
        List<String> ret=new ArrayList<>();
        HashMap<String,Integer> map=new HashMap<>();
        for(String word:words){
            if(map.get(word)==null){
                map.put(word,1);
            }else{
                int count=map.get(word);
                map.put(word,count+1);
            }
        }
        //2.建立小堆，用topK选出前k大的单词
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for(Map.Entry<String,Integer> entry: map.entrySet()){
            if(minHeap.size()<k){
                minHeap.add(entry);
            }else {
                Map.Entry<String,Integer> peek=minHeap.peek();
                if(entry.getValue().compareTo(peek.getValue())>0){
                    minHeap.poll();
                    minHeap.add(entry);
                }
                if(entry.getValue().compareTo(peek.getValue())==0){
                    if(entry.getKey().compareTo(peek.getKey())<0){
                        minHeap.poll();
                        minHeap.add(entry);
                    }
                }
            }
        }
       while(!minHeap.isEmpty()){
           ret.add(minHeap.poll().getKey());
       }
       Collections.reverse(ret);
       return ret;
    }
    public Node copyRandomList(Node head){
        HashMap<Node,Node> hashMap=new HashMap<>();
        Node cur=head;
        //完成整个链表值的映射
        while(cur!=null){
            Node newNode=new Node(cur.val);
            hashMap.put(cur,newNode);
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            hashMap.get(cur).next=hashMap.get(cur.next);
            hashMap.get(cur).random=hashMap.get(cur.random);
            cur=cur.next;
        }
        return hashMap.get(head);
    }

    public static void main(String[] args) {
        String[]words={"i","love","leetcode","i","love","coding"};
        List<String> ret=topKFrequent(words,3);
        System.out.println(ret);
    }
}
